package leetcode.code0220;

import java.util.TreeSet;

import leetcode.IDebug;
import leetcode.helper.HelpDebug;

/**
 * 执行用时：51 ms, 在所有 Java 提交中击败了8.80%的用户
 *
 * 内存消耗：42.1 MB, 在所有 Java 提交中击败了8.91%的用户
 *
 * 通过测试用例：53 / 53
 */
public class Solution implements IDebug {

	// abs(nums[i] - nums[j]) <= t
	// nums[i] - nums[j] <= t ; nums[i] <= t + nums[j]
	// nums[i] - nums[j] >= -t ; t - nums[j] >=nums[i]

	public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
		if (k == 0)
			return false;
		TreeSet<Long> ts = new TreeSet<>();
		int L = 0;
		int R = 1;
		ts.add((long) nums[L]);
		while (R <= k && R < nums.length) {
			Long sum = (long) (nums[R] + t);
			Long sub = (long) (t - nums[R]);
			if (((sub = ts.ceiling(sub)) != null && Math.abs(sub - nums[R]) <= t) || ((sum = ts.floor(sum)) != null && Math.abs(sum - nums[R]) <= t)) {
				return true;
			}
			ts.add((long) nums[R++]);
		}
		while (R < nums.length) {
			Long sum = (long) (nums[R] + t);
			Long sub = (long) (t - nums[R]);
			ts.remove((long) nums[L++]);
			if (((sub = ts.ceiling(sub)) != null && Math.abs(sub - nums[R]) <= t) || ((sum = ts.floor(sum)) != null && Math.abs(sum - nums[R]) <= t)) {
				return true;
			}
			ts.add((long) nums[R++]);
		}
		return false;
	}

	@Override
	public void debug1() {
		HelpDebug.compare(true, this.containsNearbyAlmostDuplicate(HelpDebug.str2array3("[1,2,3,1]"), 3, 0));
	}

	@Override
	public void debug2() {
		HelpDebug.compare(true, this.containsNearbyAlmostDuplicate(HelpDebug.str2array3("[1,0,1,1]"), 1, 2));
	}

	@Override
	public void debug3() {
		HelpDebug.compare(false, this.containsNearbyAlmostDuplicate(HelpDebug.str2array3("[1,5,9,1,5,9]"), 2, 3));
	}

	@Override
	public void debug4() {
		HelpDebug.compare(true, this.containsNearbyAlmostDuplicate(HelpDebug.str2array3("[1,0,1,1]"), 1, 2));
	}

	public void debug5() {
		HelpDebug.compare(false, this.containsNearbyAlmostDuplicate(HelpDebug.str2array3("[-2147483648,2147483647]"), 1, 1));
	}

	public void debug6() {
		HelpDebug.compare(false, this.containsNearbyAlmostDuplicate(HelpDebug.str2array3("[1,5,9,1,5,9]"), 2, 3));
	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug6();
		so.debug5();
		so.debug4();
		so.debug3();
		so.debug1();
		so.debug2();
	}

//	[-2147483648,2147483647]
//			1
//			1
//			false

}
